479E - Riding in a Lift - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define num 1000000007
#define lli long long int
#define ll long long
#define ff first 
#define ss second 
#define mp make_pair 
#define pb push_back
#define vi vector<int>
#define vlli vector<lli>
#define vvi vector<vi>
#define vvlli vector<vlli>
#define pii pair<int,int>
#define vii vector<pii>
#define imap map<int,int>
#define cmap map<char,int>
#define uimap unordered_map<int,int>
#define ucmap unordered_map<char,int>
#define INF 1e18
#define le length
#define debug(n1) cout << n1 << "\n"
#define rep(i , j , n) for(ll i = j ; i <= n ; i++) 
#define per(i , j , n) for(ll i = j ; i >= n ; i--)

//vi(n,fill) vector<int> v(n,fill)
//vvi(n,m,t) vector<vector<int>> dvec(n,vi(m,t))
ll binary_search(ll dp[] , ll n , ll key) { 
    ll s = 1; 
    ll e = n; 
    while(s <= e) { 
        ll mid = (s + e) / 2; 
        if(dp[mid] == key) return mid; 
        else if (dp[mid] > key) e = mid - 1; 
        else s = mid + 1; 
    } 
    return -1; 
}
//to recursively traverse on neighbours of in index.
void recNeighbours(vector<vector<char>>&a,int x,int y,int n,int m){
    if(x-1>=0 && a[x-1][y]=='O'){
        a[x-1][y]='*';
        // check(a,x-1,y,n,m);
    }
    if(x+1<n && a[x+1][y]=='O'){
        a[x+1][y]='*';
        // check(a,x+1,y,n,m);
    }
    if(y-1>=0 && a[x][y-1]=='O'){
        a[x][y-1]='*';
        // check(a,x,y-1,n,m);
    }
    if(y+1<m && a[x][y+1]=='O'){
        a[x][y+1]='*';
        // check(a,x,y+1,n,m);
    }
}
string stringToBinary(ll s) { 
    string res = ""; 
    while(s != 0) { 
        res += (char)('0' + s % 2); 
        s /= 2; 
    } 
    reverse(res.begin() , res.end()); 
    return res; 
} 
bool palin(string s) { 
    ll i = 0; 
    ll j = s.le() - 1; 
    while(i <= j) { 
        if(s[i] != s[j]) return false; 
        j-- , i++; 
    } 
    return true; 
} 
ll stoi(string s) { 
    ll val = 0; 
    ll po = 1; 
    per(i , s.le() - 1 , 0) { 
        val += po * (s[i] - '0'); 
        po *= 10; 
    } 
    return val; 
}
void countsort(vector<int> &v){
    int cnt[100001]={0};
    for(int i=0;i<v.size();i++){
        cnt[v[i]]++;
    }
    int j=0;
    for(int i=0;i<100001;i++){
        while(cnt[i]--){
            v[j]=i;
            j++;
        }
    }
}
void FastDoubling(int n, int res[]){
    //res[0] will have nth fibonacci number.
    //Pass res[2]={0}; in res[].
    if (n == 0) {
        res[0] = 0;
        res[1] = 1;
        return;
    }
    FastDoubling((n / 2), res);
    int a = res[0];
    int b = res[1];
    int c = 2 * b - a;
    if (c < 0)
        c += num;
    c = (a * c) % num;
    int d = (a * a + b * b) % num;
    if (n % 2 == 0) {
        res[0] = c;
        res[1] = d;
    }
    else {
        res[0] = d;
        res[1] = c + d;
    }
}
long fastPower(long a,long b){
    long res = 1;
    while(b>0){
        if((b&1)!=0){
            res=(res*a%num)%num;
        }
        a=(a%num*a%num)%num;
        b>>=1;
    }
    return res;
}
void sumOfDivisors(vector<int> &v,int n){
for(int i=1;i<=n;i+=1){
    for(int d=i;d<=n;d+=i){
        v[d]+=i;
    }
}
}
void seiveOfEratosthenes(vector<int> &v,int n){
    //Pass vector filled with 1s
    v[0]=0;
    v[1]=0;
   for(int i=2;i*i<=n;i++){
       for(int j=2*i;j<=n;j+=i){
           v[j]=0;
       }
   }
}
void comb(vector<vector<lli> > &v,int n){
    for(int i=0;i<n;i++){
        vector<long long int> v1;
        for(int j=0;j<n;j++){
            v1.push_back(0);
        }
        v.push_back(v1);
    }
    for(int i=0;i<n;i++){
        v[i][0]=1;
    }
    for(int j=1;j<n;j++){
        v[0][j]=0;
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<n;j++){
            v[i][j]=(v[i-1][j-1]+v[i-1][j]);
            //v[i][j]=(v[i-1][j-1]+v[i-1][j])%num;
        }
    }
}
int NoofDivisors(int val){
    int ans=0;
    for(int i=1;i*i<=val;i++){
        if(val%i==0){
            if(val/i==i){
                ans++;
            }
            else{
                ans+=2;
            }
        }
    }
    return ans;
}
int sumofDigits(lli val){
    int sum = 0;
    for(lli copy=val;copy!=0;copy/=10){
        sum+=copy%10;
    }
    if(sum>9){
        sum=sumofDigits(sum);
    }
    return sum;
}

long long highestPowerof2(long long N)
{
    // if N is a power of two simply return it
    if (!(N & (N - 1)))
        return N;
    // else set only the most significant bit
    return 0x8000000000000000 >> (__builtin_clzll(N));
}
pair<int,int> getRange(int x,int b,int n){
    if(x>b){
        return {b+1,min(2*x-b-1,n)};
    }
    else if(x<b){
        return {max(1,2*x-b+1),b-1};
    }
    else{
        return {b,b};
    }
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,a,b,k;
cin>>n>>a>>b>>k;
vector<vector<lli>> ps(2,vector<lli> (n+1,0));
vector<vector<lli>> dp(2,vector<lli> (n+1,0));
for(int i=1;i<=n;i++){
    dp[0][i]=1;
    ps[0][i]+=ps[0][i-1]+1;
}
for(int j=1;j<=k;j++){
    for(int i=1;i<=n;i++){
        dp[1][i] = 0;
        ps[1][i] = 0;
    }
    for(int i=1;i<=n;i++){
        pair<int,int> p = getRange(i,b,n);
        dp[1][i] = (ps[0][p.second]%num-ps[0][p.first-1]%num-dp[0][i]%num+2*num)%num;
        ps[1][i] = (ps[1][i]%num+ps[1][i-1]%num+dp[1][i]%num)%num;
    }
    for(int i = 0; i <= n; i++){
		ps[0][i] = ps[1][i];
		dp[0][i] = dp[1][i];
	}
}
cout<<dp[0][a]<<"\n";
return 0;
}